# leetcode:https://leetcode.cn/problems/product-of-array-except-self/description/

"""
题目：除自身以外数组的乘积
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

"""
from typing import List

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:

        #自己能想到的时间复杂度是o(n^2，需要0到n的循环，然后再乘的循环。)

        # ans=[]
        # for i in range(len(nums)):
        #     multi=1
        #     for j,num in enumerate(nums):
        #         if i!=j:
        #             multi*=num
        #     i+=1  
        #     ans.append(multi)

        # return ans

        #真正解法：实际上，核心是怎么把嵌套循环变成外部循环呢？
        # answer[i] 等于 nums 中除了 nums[i] 之外其余各元素的乘积。换句话说，如果知道了 i 左边所有数的乘积，以及 i 右边所有数的乘积，就可以算出 answer[i]。
        #时间复杂度就变成了2n；也就是n
        n=len(nums)
        prefix=[1]*n#前缀积
        suffix=[1]*n#后缀积，这样后续取出i前的前缀积以及i处对应的后缀积就可以做出来了


        for i in range(n):
            prefix[i]=prefix[i]*nums[i]

            j=n-1-i
            suffix[i]=suffix[j]*nums[i]

        print(prefix)
        print(suffix)



        ans=[]
        for i in range(len(nums)):
            # multi=prefix[i]*suffix[i]
            # ans.append(multi)
            pass




    






#示例

nums = [1,2,3,4]
# 输出: [24,12,8,6]
solution=Solution()
ans=solution.productExceptSelf(nums)
print(ans)


nums = [-1,1,0,-3,3]
# 输出: [0,0,9,0,0]
solution=Solution()
ans=solution.productExceptSelf(nums)
print(ans)